#include "function.h"

void Midpost(Tree tree)
{
    if(tree!=NULL)
    {
        Midpost(tree->lchild);
        printf("%c",tree->data);
        Midpost(tree->rchild);
    }
}
void Tailpost(Tree tree)
{
    if(tree!=NULL)
    {
        Tailpost(tree->lchild);
        Tailpost(tree->rchild);
        printf("%c",tree->data);
    }
}
void LevelPost(Tree T)
{
    LinkQueue  Q;
    InitQueue(Q);
    Tree p;
    InQueue(Q,T);//树根入队
    while(!IsEmpty(Q))
    {
        DeQueue(Q,p);//出队当前结点并打印
        putchar(p->data);
        if(p->lchild!=NULL)
            InQueue(Q,p->lchild);
        if(p->rchild!=NULL)
            InQueue(Q,p->rchild);
    }

}
int main() {
    Tree tree=NULL;
    Tree pnew;
    ptag phead=NULL,ptail=NULL,pcur=NULL,listpnew=NULL;
    char input;
    while(scanf("%c",&input))
    {
        if(input=='\n')
        {
            break;
        }
        pnew=(Tree) calloc(1,sizeof(Bitree));
        pnew->data=input;
        listpnew=(ptag) calloc(1,sizeof(tag_t));
        listpnew->p=pnew;
        if(NULL==tree)
        {
            tree=pnew;
            pcur=listpnew;
            phead=listpnew;
            ptail=listpnew;
        }
        else{
            ptail->pnext=listpnew;
            ptail=listpnew;
            if(NULL==pcur->p->lchild)
            {
                pcur->p->lchild=pnew;
            }
            else if(NULL==pcur->p->rchild)
            {
                pcur->p->rchild=pnew;
                pcur=pcur->pnext;
            }
        }

    }
    printf("============mid post==============\n");
    Midpost(tree);
    printf("\n===========tail post=============\n");
    Tailpost(tree);
    printf("\n===========Post=============\n");
    LevelPost(tree);
    return 0;
}
